package day_2022_12_to_3.year2023;

/**
 * @author haomin
 * @date 2023/04/04 20:57
 **/
public class Day4_4_Num1000 {
    class Solution {
        public int mergeStones(int[] stones, int step) {
            int n = stones.length;
            if ((n - 1) % (step - 1) != 0) return -1;
            int[] sum = new int[n + 1];
            int[][] f = new int[n][n];
            for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
            for (int j = 1; j < n; j++) {
                for (int i = j - 1; i >= 0; i--) {
                    f[i][j] = 0x3f3f3f3f;
                    for (int k = i; k < j; k += step - 1) {
                        f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j]);
                    }
                    if ((j - i) % (step - 1) == 0) f[i][j] += sum[j + 1] - sum[i];
                }
            }
            return f[0][n - 1];
        }
    }
}